// 题目描述
// 92. 反转链表 II
// 难度
// 中等
// 1608
// 给你单链表的头指针 head 和两个整数 left 和 right ，其中 left <= right 。请你反转从位置 left 到位置 right 的链表节点，返回 反转后的链表 。
//   示例 1：
// 输入：head = [1,2,3,4,5], left = 2, right = 4
// 输出：[1,4,3,2,5]
// 示例 2：
// 输入：head = [5], left = 1, right = 1
// 输出：[5]
//   提示：
// 链表中节点数目为 n
// 1 <= n <= 500
// -500 <= Node.val <= 500
// 1 <= left <= right <= n
//   进阶： 你可以使用一趟扫描完成反转吗？
// 通过次数415,172提交次数745,380
// https://leetcode.cn/problems/reverse-linked-list-ii/

function ListNode(val, next) {
  this.val = (val === undefined ? 0 : val)
  this.next = (next === undefined ? null : next)
}

/**
 * 递归反转链表
 * @param head
 * @returns ListNode
 */
function reverse(head) {
  if (head === null || head.next === null) {
    return head
  }

  // last 是最后一个节点
  const last = reverse(head.next)
  // 反转链表
  head.next.next = head
  // 断链
  head.next = null

  return last
}

// 反转以 head 为起点的 n 个节点，返回新的头结点
function reverseN(head, n) {
  if (n === 1) {
    // 记录第 n + 1 个节点
    successor = head.next
    return head
  }

  // 以 head.next 为起点，需要反转前 n - 1 个节点
  const last = reverseN(head.next, n - 1)
  // 反转链表
  head.next.next = head
  // 让反转之后的 head 节点和后面的节点连起来
  head.next = successor

  return last
}

/**
 * @param {ListNode} head
 * @param {number} left
 * @param {number} right
 * @return {ListNode}
 */
var reverseBetween = function (head, left, right) {
  // base case
  if (left === 1) {
    // 反转以head开头的n个节点
    return reverseN(head, right)
  }

  // 将 head.next 作为起点反转前 left - 1 个节点
  head.next = reverseBetween(head.next, left - 1, right - 1)

  return head
}

const lst = new ListNode(1, new ListNode(2))
const newList = reverse(lst)
console.log(newList)
